/**
* Created with IntelliJ IDEA.
* Description:
* User:DELL
* Date:2025-04-22
* Time:23:59
*/
public class Text {
    public void reorderList(ListNode head) {
        //处理边界情况
        if(head==null||head.next==null||head.next.next==null){
            return;
        }
        //1.找中间节点--快慢指针
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //2.逆序slow.next后半部分的链表---头插法
        ListNode head2=new ListNode(0);
        ListNode cur=slow.next;
        slow.next=null;//分离链表
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=head2.next;
            head2.next=cur;
            cur=next;
        }
        //3.合并两个链表--双指针
        ListNode cur1=head,cur2=head2.next;
        ListNode ret=new ListNode(0);
        ListNode prev=ret;
        while(cur1!=null){//因为一定是cur1比cur2长
            prev.next=cur1;
            prev=cur1;
            cur1=cur1.next;
            if(cur2!=null){
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
    }
}
